package LimitedTimeGame.Day_0218;

/**
 * @author zxc
 * @date 2023/02/18 10:20
 **/

import java.util.Stack;

/**
 * 题目 ：验证栈序列
 * 题目详述 ：
 * 给定pushed和popped两个序列，每个序列中的 值都不重复，
 * 只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false。
 *
 * 提示：
 * 1 <= pushed.length <= 1000
 * 0 <= pushed[i] <= 1000
 * pushed 的所有元素 互不相同
 * popped.length == pushed.length
 * popped 是 pushed 的一个排列
 *
 *
 */
public class ValidateStackSequences {
    /**
     * 思路 ：
     * 利用栈的数据结构，来实现看是否最终栈为空
     * @param pushed
     * @param popped
     * @return
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int pushLen = pushed.length;
        int p1 = 0;
        int p2 = 0;
        while(p1 <= pushLen){
            if(!stack.isEmpty() && stack.peek() == popped[p2]){
                stack.pop();
                p2++;
            }
            else {
                if(p1 < pushLen){
                    stack.push(pushed[p1]);
                }
                p1++;
            }
        }
        return stack.isEmpty();
    }
}
